//反转链表的i和i+1个位置，反转过 的不需要再反转
//递归和非递归写法
/*
 *
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
// class Solution {
// public:
//     ListNode* swapPairs(ListNode* head) {
//         ListNode* dummy=new ListNode(-1);
//         dummy->next=head;
//         ListNode* node0=dummy,*node1=head;
//         //node1是当前要交换的两个节点的第一个节点
//         while(node1&&node1->next)
//         {
//             ListNode* node2=node1->next;
//             ListNode* node3=node2->next;

//             node0->next=node2;
//             node2->next=node1;
//             node1->next=node3;

//             node0=node1;
//             //node3是下一个要交换的两个节点的第一个节点
//             node1=node3;
//         }
//         return dummy->next;
//     }
// };
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head==nullptr||head->next==nullptr)return head;

        ListNode* node1=head;
        ListNode* node2=node1->next;
        ListNode* node3=node2->next;
        
        node1->next=swapPairs(node3);
        node2->next=node1;
        return node2;
    }
};
